/*
 * @Author       : wangzeyu 2309335887@qq.com
 * @Date         : 2023-06-29 10:25:57
 * @LastEditors  : WangZeYu
 * @LastEditTime : 2023-06-29 13:48:26
 * @FilePath     : \algorithm\mergeSort.js
 * @Description  : 归并排序(分治算法)
 */
function mergeSort(arr){
  console.log('递归调用:',arr)
  if(arr.length <= 1){
    return arr
  }
  let m = Math.floor(arr.length / 2)
  let left = mergeSort(arr.slice(0, m))
  let right = mergeSort(arr.slice(m, arr.length))
  let result = merge(left, right)
  return result
}
function merge(left, right){
  let result = []
  let i = 0,j = 0
  console.log('左数组:',left,'右数组:',right)

  while(i < left.length && j < right.length){
    if(left[i] < right[j]){
      result.push(left[i])
      i++
    }else{
      result.push(right[j])
      j++
    }
  }
  // 为应对 1.一个数组所有项都大于另一个数组
  // 2.两个数组长度不一样，可能会有一个数组有剩余
  if(i < left.length){
    result.push(...left.slice(i))
  }else{
    result.push(...right.slice(j))
  }
  return result
}

let a = [3,5,4,2,1,15]

console.log(mergeSort(a))